#include "BloqueHoja.h"
#include "../../claves/TipoClave.h"
#include "Arbol.h"
#include "../../FuncionesUtiles.h"

BloqueHoja::BloqueHoja(Arbol* a, cantBytes tamanio, TipoClave* extractor) :
	BloqueArbol(a, tamanio,extractor) {

	this->tipo = 'H';
	this->extractor = extractor;
	this->setHermano(ID_NULL);
	this->setPadre(ID_NULL);
}

BloqueHoja::~BloqueHoja() {

}

char BloqueHoja::getTipo() {

	return this->tipo;
}

offset BloqueHoja::getSiguiente() {

	return this->siguiente;
}


Bytes BloqueHoja::serializarse() {
	/*tipo|id|padre|siguiente|claves|punteros*/

	Bytes serializacion;

	serializacion.agregarAlFinal(&this->tipo,sizeof(this->tipo));

	serializacion.agregarAlFinal(&this->id,sizeof(this->id));

	serializacion.agregarAlFinal(&this->padre,sizeof(this->padre));

	serializacion.agregarAlFinal(&this->siguiente,sizeof(offset));

	serializacion.agregarAlFinal(BloqueArbol::serializarse());

	if (serializacion.getTamanio() < this->tamanio) {
		serializacion.agregarAlFinal(crearBytesNulos(this->tamanio - serializacion.getTamanio()));
	}

	return serializacion;
}

bool BloqueHoja::hidratarse(const Bytes& bytes) {

	/*tipo|id|padre|offset siguiente|claves|punteros*/

	offset offsetActual = 0;
	bytes.leer(&this->tipo,offsetActual,sizeof(this->tipo));

	offsetActual += sizeof(this->tipo);

	bytes.leer(&this->id,offsetActual,sizeof(this->id));

	offsetActual += sizeof(this->id);

	bytes.leer(&this->padre,offsetActual,sizeof(this->padre));
	offsetActual += sizeof(this->padre);

	bytes.leer(&this->siguiente,offsetActual,sizeof(this->siguiente));

	offsetActual += sizeof(this->siguiente);
	BloqueArbol::hidratarse(bytes.getSubBytes(offsetActual,bytes.getTamanio() - offsetActual));

	return true;
}

BloqueArbol* BloqueHoja::getHijoMenor() {
	return this;

}
void BloqueHoja::setHermano(offset hermano) {
	this-> siguiente = hermano;
}

offset BloqueHoja::getElemento(const Key& clave, Resultado& res) {
	bool encontrado = false;
	unsigned i = 0;

	while ((!encontrado) && (i < punteros.size())) {
		if (clave == claves[i]) {
			encontrado = true;
			res = RES_OK;
			return punteros[i];
		}
		i++;
	}
	res = RES_INEXISTENTE;
	return ID_NULL;
}

BloqueArbol* BloqueHoja::buscarHijo(const Key& claveABuscar) {
	/*fin de la llamada recursiva.*/
	return this;
}

BloqueHoja* BloqueHoja::getHermano() {

 if( siguiente ==ID_NULL){
	 return NULL;
 }
		 return dynamic_cast<BloqueHoja*> (arbol->get(siguiente));
}

/*si puede balancear (quedan ambas hojas en estado valido), lo hace
 * y retorna true, sino puede retorna false*/
/*PRE: debe recibirlos en el orden que se balancearan*/
/*ojo solo se usa para Overflow*/
bool BloqueHoja::balancearDosHojas(BloqueHoja* nodo, BloqueHoja* hermano) {
	Key claveAnterior = nodo->getClaveMayor();

	/*voy a poder mergear esos 2 hermanos y ninguno dara overflow*/
	if (!nodo->existeOverflow(hermano->getCantClaves())) {

		BalancearDos(nodo, hermano, false);
		/* debo cambiar la clave en el padre*/
		Key claveNueva = nodo->getClaveMayor();
		BloqueInterno* padre = dynamic_cast<BloqueInterno*> (arbol->get(
				nodo->getPadre()));
		padre->cambiarClave(claveAnterior, claveNueva);
		padre->setModificado();
		return true;
	}
	return false;
}

Resultado BloqueHoja::mergeTresHojas(BloqueHoja* hermanoIzq, BloqueHoja* nodo,
		BloqueHoja* hermano, bool tresADos) {

	Key claveAnteriorMedio;
	Key claveAnteriorIzq;
	if (nodo->getCantClaves() != 0) {
		claveAnteriorMedio = nodo->getClaveMayor();
	}
	if (hermanoIzq->getCantClaves() != 0) {
		claveAnteriorIzq = hermanoIzq->getClaveMayor();
			}
	Key clavenn;
	unsigned posicion =0;
	if(tresADos){
	clavenn = nodo->getClaveMayor();
	}
	BalancearTres(hermanoIzq, nodo, hermano, tresADos);
	/* debo cambiar la clave en el padre*/

	Key claveNueva;
	if (tresADos) {

			BloqueInterno* padre = dynamic_cast<BloqueInterno*> (arbol->get(
					hermano->getPadre()));

			BloqueArbol* arb = padre->buscarUnHijo(clavenn,posicion);
			if(arb ==NULL){
				cerr<<"Me da un nodo nulo cuando nunca debería suceder esto"<<__FILE__<<__LINE__<<std::endl;

			}

			Resultado resultadoHijo = padre->removerClaveEHijo(padre->getClaves()[posicion],
					nodo);


	if (hermanoIzq->getCantClaves() != 0) {

		claveNueva = hermanoIzq->getClaveMayor();
		BloqueInterno* padre = dynamic_cast<BloqueInterno*> (arbol->get(
				hermano->getPadre()));

		claveAnteriorIzq = padre->getClaves()[posicion-1];
		padre->cambiarClave(claveAnteriorIzq, claveNueva);
		padre->setModificado();

		} else {
		std::cerr << "problemas" << __FILE__ << __LINE__ << std::endl;
		}


		padre->setModificado();
		hermanoIzq->setHermano(hermano->getId());
		nodo->setBorrado();

		return resultadoHijo;
	} else {
		nodo->setPadre(hermanoIzq->getPadre());
		if (nodo->getCantClaves() != 0) {
			BloqueInterno* padre = dynamic_cast<BloqueInterno*> (arbol->get(
					hermanoIzq->getPadre()));
			padre->addClaveEHijo(nodo->getClaveMayor(), nodo->getId());
			padre->actualizarClaves();
			/*uno los hermanos*/


			padre->setModificado();
			hermanoIzq->setHermano(nodo->getId());
			nodo->setHermano(hermano->getId());

		} else {
			std::cerr << "el nodo nodo quedo con cero claves" << __FILE__
					<< __LINE__ << std::endl;
		}
	}
	return RES_OK;

}

/*Retorno el nodo donde estaba ese elemento que se inserto,
 * el resultado de la operacion se retorna res, Si no se pue realizar la operacion
 * en el retorno se devuelve NULL */
BloqueInterno* BloqueHoja::overflowRaizHoja(Resultado& res) {

	BloqueHoja* nodo = this;
	if (nodo->getPadre() != ID_NULL) {
		std::cerr << "el nodo  tiene padre y no debería tener" << __FILE__
				<< __LINE__ << std::endl;
	}

	BloqueHoja* nodoHermano = dynamic_cast<BloqueHoja*> (arbol->getNew('H'));
	BloqueHoja* nodoHermano2 = dynamic_cast<BloqueHoja*> (arbol->getNew('H'));
	/*ahora debere crearles un padre con las claves y el mismo sera raiz*/
	/*no imp el retorno puesto es siempre verdadero, siempre tengo espacio si el otro es nuevo*/
	/*retorno la raiz nueva*/
	BloqueInterno* nodoPadre =
			dynamic_cast<BloqueInterno*> (arbol->getNew('I'));
	return nodoPadre->mergeRaizHoja(nodoHermano2, nodo, nodoHermano, res);
}


void BloqueHoja::actualizarSiguiente(){

	BloqueInterno* padre = dynamic_cast<BloqueInterno*> (arbol->get(this->getPadre()));
	vector<offset> padreoffsets = padre->getPunteros();
	for(unsigned i=0;i<padreoffsets.size()-1;i++){
		if(padreoffsets[i] == this->id){
			this->setHermano(padreoffsets[i+1]);
		}
	}
}




BloqueInterno* BloqueHoja::overflowHoja(Resultado& res) {
	BloqueHoja* nodo = this;
	BloqueInterno* padre = dynamic_cast<BloqueInterno*> (arbol->get(
			nodo->getPadre()));
	if (padre != NULL) {
		BloqueHoja* hermano = dynamic_cast<BloqueHoja*> (padre->getHijoDerecho(
				nodo->getId()));
		/*intento con un solo hermano, si no puedo debere usar el de la izquiera*/
		if (hermano != NULL) {
			if (!(BloqueHoja::balancearDosHojas(nodo, hermano))) {
				/*NO pude mergear esos 2 hermanos */
				/*no se pudieron balancear y por lo tanto creare un nuevo nodo que ira entremedio de los dos nodos*/
				BloqueHoja* nuevoNodo =
						dynamic_cast<BloqueHoja*> (arbol->getNew('H'));
				/*false por q es overflow*/
				res = mergeTresHojas(nodo, nuevoNodo, hermano, false);
			}
		} else {
			/*no tengo a la derecha, veo a la izquierda*/
			BloqueHoja* hermanoIzq =
					dynamic_cast<BloqueHoja*> (padre->getHijoIzquierdo(
							nodo->getId()));
			/*intento con un solo hermano, si no puedo debere usar el de la izquiera*/
			if (hermanoIzq != NULL) {
				if (!balancearDosHojas(hermanoIzq, nodo)) {
					/*NO pude mergear esos 2 hermanos */
					/*no se pudieron balancear y por lo tanto creare un nuevo nodo que ira a entremedio de los dos nodos*/
					BloqueHoja* nuevoNodo =
							dynamic_cast<BloqueHoja*> (arbol->getNew('H'));
					/*false por q es overflow. se agrega al padre pero ojo, padre puede tener overflow*/

					res = mergeTresHojas(hermanoIzq, nuevoNodo, nodo, false);
				}
			}

		}

	}
	return NULL;
}

/*si puede balancear (quedan ambas hojas en estado valido), lo hace
 * y retorna true, sino puede retorna false*/
/*PRE: debe recibirlos en el orden que se balancearan*/
/*ojo solo se usa para underflow*/
bool mergeDosHojas(BloqueHoja* nodo, BloqueHoja* nodoHermano) {
	/*voy a poder mergear esos 2 hermanos y ninguno dara underflow*/
	if (!nodo->existeUnderflow(nodoHermano->getCantClaves())) {
		/*se pueden balancear*/
		BalancearDos(nodo, nodoHermano, false);
		return true;
	}
	return false;
}


bool BloqueHoja::dosAUno(BloqueHoja* nodoHermano) {
	Key claveAnterior;
	BloqueHoja* nodo = this;
	/*voy a poder mergear esos 2 hermanos y ninguno dara overflow*/
	if (!nodo->existeOverflow(nodoHermano->getCantClaves())) {
		/*se pueden balancear*/
		BalancearDos(nodo,nodoHermano,true);
		/* debo cambiar la clave en el padre*/
		nodo->setBorrado();
		return true;

	}
	return false;
}
BloqueInterno* BloqueHoja::underflowHoja(Resultado& res,
		const Key& claveViejaNodo) {
	BloqueHoja* nodo = this;
	BloqueInterno* padre = dynamic_cast<BloqueInterno*> (arbol->get(
			nodo->getPadre()));
	/*tiene un padre => tiene hermano/s */
	BloqueHoja* hermano = dynamic_cast<BloqueHoja*> ((padre)->getHijoDerecho(
			claveViejaNodo));

	/*intento con un solo hermano, si no puedo debere usar el de la izquierda*/
	if (hermano != NULL) {/*tiene hermano derecho*/
		if (mergeDosHojas(nodo, hermano)) {
			/* debo cambiar la clave en el padre*/
			Key claveNueva = nodo->getClaveMayor();
			padre->cambiarClave(claveViejaNodo, claveNueva);
			padre->actualizarClaves();
			padre->setModificado();
			res = RES_OK;
		} else {/*NO se mergiaron*/
			/*intento mergear con el de la izquierda*/

			BloqueHoja* hermanoIzq =
					dynamic_cast<BloqueHoja*> (padre->getHijoIzquierdo(
							claveViejaNodo));
			if (hermanoIzq != NULL) { /*tiene hermano izquierdo*/
				Key claveAnterior = hermanoIzq->getClaveMayor();
				if (mergeDosHojas(hermanoIzq, nodo)) {
					Key claveNueva = hermanoIzq->getClaveMayor();
					(padre)->cambiarClave(claveAnterior, claveNueva);
					padre->setModificado();
					res = RES_OK;
				} else {
					/*NO se mergiaron*/
					/*Existen mis dos hermanos y no me pude mergear con ninguno, por lo que
					 * de los tres me quedare con solamente dos completos*/
					res = mergeTresHojas(hermanoIzq, nodo, hermano, true);
					hermanoIzq->setHermano(hermano->getId());
					hermanoIzq->setModificado();

				}
			} else {
				/*tengo hermano derecho pero no izquierdo intento con el derecho del derecho*/
				BloqueHoja* hermanoDer =
						dynamic_cast<BloqueHoja*> (padre->getHijoDerecho(hermano->getMayorDeRama()));
				if (hermanoDer != NULL) {/*existe*/

					res = mergeTresHojas(nodo, hermano, hermanoDer, true);
					nodo->setHermano(hermanoDer->getId());
					hermano->setBorrado();
					nodo->setModificado();
				} else {
					/*solo existe el q explota y un hermano con quien no se pueden mergear*/
					if (nodo->getCantClaves() == 0) {
						nodo->setBorrado();
					} else {
						if (!this->dosAUno(hermano)) {
							std::cerr
									<< "dos nodos en underflow que no se pueden unir en uno solo"
									<< __FILE__ << __LINE__ << std::endl;
						}
					}
				}

			}
		}

	} else {/*no tengo hermano derecho*/
		/*intento mergear con el de la izquierda*/
		BloqueHoja* hermanoIzq =
				dynamic_cast<BloqueHoja*> (padre->getHijoIzquierdo(
						claveViejaNodo));
		if (hermanoIzq != NULL) { /*tiene hermano izquierdo*/
			Key claveAnterior = hermanoIzq->getClaveMayor();
			if (mergeDosHojas(hermanoIzq, nodo)) {
				Key claveNueva = hermanoIzq->getClaveMayor();
				padre->cambiarClave(claveAnterior, claveNueva);
				padre->setModificado();
				res = RES_OK;
			} else {
				BloqueHoja* hermanoIzqIzq =
						dynamic_cast<BloqueHoja*> (padre->getHijoIzqIzq(
								claveViejaNodo));
				if (hermanoIzqIzq != NULL) {
					res = this->mergeTresHojas(hermanoIzqIzq, hermanoIzq, nodo,
							true);
					hermanoIzq->setBorrado();
					hermanoIzqIzq->setHermano(nodo->getId());
					hermanoIzqIzq->setModificado();
				} else {

					if (nodo->getCantClaves() == 0) {
						nodo->setBorrado();
					} else {
						if (!hermanoIzq->dosAUno(this)) {
							std::cerr
									<< "dos nodos en underflow que no se pueden unir en uno solo"
									<< __FILE__ << __LINE__ << std::endl;
						}
					}

				}

			}
		} else {
			std::cerr << "un nodo en underflow que no tiene hermanos "
					<< __FILE__ << __LINE__ << std::endl;
		}
	}
	return padre;
}

BloqueInterno* BloqueHoja::resolverOverflow() {
	Resultado res;

	/*la hoja que explota tiene hermanos*/
	return this->overflowHoja(res);
}

void BloqueHoja::resolverUnderflow(const Key& claveVieja) {
	Resultado res;
	this->underflowHoja(res, claveVieja);

}

BloqueArbol* BloqueHoja::insertarElemento(const Elemento& elemento,
		Resultado& res, bool& overflow) {
	std::vector<Key>::iterator it = this->claves.begin();
	std::vector<offset>::iterator itP = this->punteros.begin();
	bool inserto = false;
	res = RES_DUPLICADO;
	while (!inserto && (it != claves.end())) {
		if (elemento.getClave() < (*it)) {
			inserto = true;
			claves.insert(it, elemento.getClave());
			punteros.insert(itP, elemento.getDato());
			res = RES_OK;
		} else {
			if (elemento.getClave() == (*it)) {
				res = RES_DUPLICADO;
				return NULL;
			}
		}
		it++;
		itP++;
	}
	if (!inserto) {
		claves.push_back(elemento.getClave());
		punteros.push_back(elemento.getDato());
		res = RES_OK;

	}
	/*Aca la clave ya esta insertada. vemos overflow*/

	if (this->id == ID_RAIZ){
		if(claves.size() == (2 * this->getCantClavesMax())){
			/*esta hoja que exploto es la raiz*/
			BloqueInterno* nuevoPadre = this->overflowRaizHoja(res);
			return nuevoPadre;
		}
		overflow = false;
			this->setModificado();
			return this;

	} else {

		if (claves.size() > this->getCantClavesMax()) {
			overflow = true;
			/*tuve overflow, se lo aviso a mi papa, PERO yo resulvo mi overflow*/
			/*le avisa asi el se fija en que estado quedo el*/
			this->resolverOverflow();
			this->setModificado();
			arbol->get(this->getPadre())->actualizarClaves();
			return arbol->get(this->getPadre());
		} else {

			overflow = false;
			this->setModificado();
			return this;
		}
	}

}

BloqueArbol* BloqueHoja::removerElemento(const Elemento& elemento,
		Resultado& res) {
	Key claveABorrar = elemento.getClave();
	std::vector<Key>::iterator it = this->claves.begin();
	std::vector<offset>::iterator itP = this->punteros.begin();
	bool borro = false;
	res = RES_INEXISTENTE;
	while (!borro && (it != claves.end())) {
		if (claveABorrar == (*it))

		{
			claves.erase(it);
			punteros.erase(itP);
			borro = true;
			res = RES_OK;
		}
		it++;
		itP++;
	}

	if (borro) {
		if (this->getPadre() != ID_NULL) {
			if (claves.size() < this->getCantClavesMin()) {
				this->resolverUnderflow(elemento.getClave());
				if(arbol->get(this->getPadre())->getCantClaves() != 0){
				arbol->get(this->getPadre())->actualizarClaves();
				}
			}else{
				this->setModificado();
			}
		}
	} else {
		res = RES_INEXISTENTE;
	}

	this->setModificado();
	return arbol->getRaiz();
}

std::string BloqueHoja::clavesToString() {

	std::stringstream st;
	st << "H ("<<this->getId()<< ", "<<this->getPadre()<< ", "<<this->siguiente<< ")";


	for (unsigned i = 0; i < claves.size(); i++) {
		st << claves[i].toString() << "["<<punteros[i]<<"]; ";
	}
	st << std::endl;
	return st.str();

}

Key BloqueHoja::getMayorDeRama() {
	if (this->getCantClaves() > 0) {
		return this->getClaveMayor();
	} else {
		if (this->getPadre() != ID_NULL) {
			BloqueInterno* padre = dynamic_cast<BloqueInterno*> (arbol->get(
					this->getPadre()));
			if (padre->getCantClaves() > 0) {
				return padre->getClaveMayor();
			}
		}
	}
	return Key();
}

unsigned BloqueHoja::getCantClaves() const {
	return this->claves.size();
}

void BloqueHoja::imprimir() {
	std::cout << clavesToString();
}
